package week01;


public class T002 {
	
	//方法一：递归
//	public static void main(String[] args) {
//		int sum=0;
//		int i;
//		for(i=1;;i++) {
//			int n=fib(i);
//			if(n<=4000000&&n%2==0) {
//				sum+=n;
//			}
//			if(n>4000000) break;
//		}
//		System.out.println(sum);
//	}
//	
//	public static int fib(int n) {
//		if(n==1) return 1;
//		if(n==2) return 2;
//		return fib(n-1)+fib(n-2);
//	}
	
//	//常规数组解法   时间复杂度：O(n)   空间复杂度：O(n)
//	public static void main(String[] args) {
//		int n=4000000;
//		int[] a = new int [n+1];
//		int sum=2,i;
//		a[0]=1;a[1]=2;
//		for(i=2;;i++) {
//			a[i]=a[i-1]+a[i-2];
//			if(a[i]%2==0&&a[i]<=4000000) {
//				sum+=a[i];
//			}
//			if(a[i]>4000000) break;
//		}
//		System.out.println(sum);
//	}
	
//	//变量交替  时间复杂度：O(n)   空间复杂度：O(1)
//	public static void main(String[] args) {
//		int a=1,b=2;
//		int sum=0,temp=0;
//		while(b<=4000000) {
//			if(b%2==0) sum+=b;
//			temp=b;
//			b=a+b;
//			a=temp;
//		}
//		System.out.println(sum);
//	}
	
//	滚动数组
//	变量交替的方式极大程度的优化了空间复杂度，但有一个致命缺陷
//	需要手动命名很多变量来赋值，在递推公式仅由前两项决定的情况下不是很明显
//	这时候需要运用到滚动数组这个知识，它的应用很多，如优化动态规划的空间复杂度
//	取模的运算可以将一个数降至0~n-1，可以通过这个重复利用数组空间
//	PS：遇到减法后取模一定要判断是否为负数，如果为负可以在取模前加一个模数
//	时间复杂度：O( n )
//	空间复杂度：O( 1 )
	
	public static void main(String[] args) {
		int [] fib = new int [3];
		fib[0]=1;fib[1]=2;
		int sum=2,end=4000000;
		int i;
		for(i=2;;i++) {
			fib[i%3] = fib[(i-1+3)%3]+fib[(i-2+3)%3];
			if(fib[i%3]>end) break;
			if((fib[i % 3] % 2) == 0) sum += fib[i % 3];
		}
		System.out.println(sum);
	}
	
	
}
